package hashTable;

/**
 * @author czt
 * @version 1.0
 * @since 2025/1/3
 * 哈希表
 * 给每份数据分配一个编号，放入表格(数组)
 * 建立编号与表格索引的关系，将来就可以通过编号快速查找数据
 *      1.理想情况编号当唯一，数组能容纳所有数据
 *      2.现实情况是不能为了容纳一个所有数据造一个超大数组，编号也可以重复
 * 解决
 *      1.有限长度的数组，以【拉链】方式存储数据
 *      2.允许编号适当重复，通过数据自身来进行区分
 *
 * hash算法
 *      hash算法就是将任意对象，分配一个编号的过程，其中编号是一个有限范围内的数字，常见的有MD5，SHA
 */
public class HashTable {

    /**
     * 问题解答:  前提(数组长度为2的n次方)
     *  为什么计算索引位置用:hash & (数组长度 - 1)    等价于 [hash % 数组长度]
     *
     *  为什么旧链表会拆分成两条，一条hash & 旧数组长度==0 另一条 !=0
     *
     *  为什么拆分后的两条链表，一个原索引不变，另一个是原索引+旧数组长度
     *
     */

    static class Entry{
        int hash; // 哈希码
        Object key; // 键
        Object value; // 值
        Entry next;

        public Entry(int hash, Object key, Object value) {
            this.hash = hash;
            this.key = key;
            this.value = value;
        }
    }

    Entry[] table = new Entry[16];
    int size = 0; // 元素个数
    float loadFactor = 0.75f; // 负载因子
    int threshold = (int) (loadFactor * table.length);

    /*
        求模运算替换为位运算
        - 前提:数组长度是2的n次方
        - hash % 数组长度等价于 hash & (数组长度-1)
            在按位与(求桶下标)、拆分链表(扩容)、高低位异或(二次哈希)中都使用到了数组容量为2的n次方的特性
     */
    // 根据hash码获取value
    Object get(int hash, Object key) {
        int idx = hash & (table.length - 1);
        // 找数组，也就是链表头
        if (table[idx] == null) {
            return null;
        }
        Entry p = table[idx];
        // 从链表头往尾部找
        while (p != null) {
            if (p.key.equals(key)) {
                return p;
            }
            p = p.next;
        }
        return null;
    }

    // 向hash表存入新key value，如果key重复，则更新value
    void put(int hash, Object key, Object value) {
        int idx = hash & (table.length - 1);
        if (table[idx] == null) {
            // 1.有空位，直接新增
            table[idx] = new Entry(hash, key, value);
        } else {
            // 2. 无空位，沿链表查找，有重复key更新，没有则新增
            Entry p = table[idx];
            while (true) {
                if (p.key.equals(key)) {
                    p.value = value;
                    return;
                }
                if (p.next == null) {
                    break;
                }
                p = p.next;
            }
            p.next = new Entry(hash, key, value); // 新增操作
        }
        size++;
        if (size > threshold) {
            // 扩容方法
            resize();
        }
    }

    /**
     * 扩容
     */
    private void resize() {
        Entry[] newTable = new Entry[table.length << 2];
        for (int i = 0; i < table.length; i++) {
            Entry p = table[i]; // 拿到每个链表头
            if (p != null) {
                // 拆分链表，移动到新数组
                /*
                    拆分规律
                        - 一个链表最多拆分为两个链表
                        - hash & table.length == 0 的一组  a组
                        - hash & table.length != 0 的一组  b组
                 */
                Entry a = null;
                Entry b = null;
                Entry aHead = null; // 链表头
                Entry bHead = null;
                while (p != null) {
                    if ((p.hash & table.length) == 0) {
                        if (a != null) {
                            a.next = p;
                        } else {
                            aHead = p;
                        }
                        // 分配到a
                        a = p;
                    } else {
                        if (b != null) {
                            b.next = p;
                        } else {
                            bHead = p;
                        }
                        // 分配到b
                        b = p;
                    }
                    p = p.next;
                }
                // 规律:a链表保持索引位置不变，b链表索引位置+table.length
                if (a != null) {
                    a.next = null;
                    newTable[i] = aHead;
                }
                if (b != null) {
                    b.next = null;
                    newTable[i + table.length] = bHead;
                }
            }
        }
        table = newTable;
        threshold = (int) (loadFactor * table.length);
    }

    // 根据hash码删除，返回删除的value
    Object remove(int hash, Object key) {
        int idx = hash & (table.length - 1);
        if (table[idx] == null) {
            return null;
        }
        Entry p = table[idx];
        Entry prev = null;
        while (p != null) {
            if (p.key.equals(key)) {
                // 找到删除
                if (prev == null) {
                    table[idx] = p.next;
                } else {
                    prev.next = p.next;
                }
                return p.value;
            }
            // 更新上一个节点
            prev = p;
            p = p.next;
        }
        return null;
    }

    public Object get(Object key) {
        int hash = key.hashCode();
        int idx = hash & (table.length - 1);
        // 找数组，也就是链表头
        if (table[idx] == null) {
            return null;
        }
        Entry p = table[idx];
        // 从链表头往尾部找
        while (p != null) {
            if (p.key.equals(key)) {
                return p;
            }
            p = p.next;
        }
        return null;
    }

    public void put(Object key, Object value) {
        int hash = key.hashCode();
        int idx = hash & (table.length - 1);
        if (table[idx] == null) {
            // 1.有空位，直接新增
            table[idx] = new Entry(hash, key, value);
        } else {
            // 2. 无空位，沿链表查找，有重复key更新，没有则新增
            Entry p = table[idx];
            while (true) {
                if (p.key.equals(key)) {
                    p.value = value;
                    return;
                }
                if (p.next == null) {
                    break;
                }
                p = p.next;
            }
            p.next = new Entry(hash, key, value); // 新增操作
        }
        size++;
        if (size > threshold) {
            // 扩容方法
            resize();
        }
    }

    public Object remove(Object key) {
        int hash = key.hashCode();
        int idx = hash & (table.length - 1);
        if (table[idx] == null) {
            return null;
        }
        Entry p = table[idx];
        Entry prev = null;
        while (p != null) {
            if (p.key.equals(key)) {
                // 找到删除
                if (prev == null) {
                    table[idx] = p.next;
                } else {
                    prev.next = p.next;
                }
                return p.value;
            }
            // 更新上一个节点
            prev = p;
            p = p.next;
        }
        return null;
    }

}
